package top;

import java.util.ArrayList;
import java.util.List;

/**
 * @author chenyw
 * @date 2022/7/20 9:53
 */
public class Top279numSquares {
/*    //动归
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j<= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] +1);
            }
        }
        return dp[n];
    }*/

    //数学判定法：四平方和定理
    public int numSquares(int n) {
        //判断1
        if(isPerfectSquares(n)) {
            return 1;
        }
        //判断4
        if (checkAnswer4(n)) {
            return 4;
        }
        //判断2
        for (int i = 1; i * i <= n; i++) {
            int j = n - i * i;
            if (isPerfectSquares(j)) {
                return 2;
            }

        }
        return 3;
    }

    private boolean checkAnswer4(int n) {
        // n = 4^k * (8*m + 7)
        while (n % 4 == 0) {
            n = n / 4;
        }
        return n % 8 == 7;
    }

    private boolean isPerfectSquares(int n) {
        int i = (int) Math.sqrt(n);
        return n == i * i;
    }


}
